// to run: ./a.out N

#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <assert.h>

struct Info
{
  std::size_t node;
  std::size_t beg;
  std::size_t end;
};



Info&
top(Info *stack, const std::size_t t)
{
  assert (t > 0);
  return stack[t-1];
}



void
push(Info *stack, std::size_t& t, const std::size_t bound, 
     std::size_t n, std::size_t b, std::size_t e)
{
  if (t == bound)
    {
      fprintf(stderr, "Stack overflow!\n");
      exit (1);
    }

  stack[t].node = n;
  stack[t].beg = b;
  stack[t].end = e;
  ++t;
}



void
pop(Info *stack, std::size_t& t)
{
  if (t == 0)
    {
      fprintf(stderr, "Stack underflow!\n");
      exit (1);
    }

  --t;
}




void
print(Info *stack, const std::size_t t)
{
  if (t > 0)
    {
      for (std::size_t i = t; i > 0; --i)
	{
	  fprintf(stderr, "%u %u %u\n", stack[i-1].node, stack[i-1].beg, stack[i-1].end);
	}
    }
  fprintf(stderr, "BOTTOM\n");
}




std::size_t
min(std::size_t n1, std::size_t n2)
{
  return n1 < n2 ? n1 : n2;
}




void
create_segment_tree(std::size_t* m, std::size_t* a, 
		    const std::size_t SIZE, std::size_t n)
{
  std::size_t node;
  std::size_t left_child;
  std::size_t right_child;
  std::size_t beg;
  std::size_t end;
  std::size_t mid;

  // use stack to eliminate recursion from 
  // http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees

  Info stack[SIZE];
  std::size_t t = 0; // mark top of the stack
  
  push(stack, t, SIZE, 0, 0, n-1);

  while (t > 0)
    {
      Info& current_range = top(stack, t);
      node = current_range.node;
      beg = current_range.beg;
      end = current_range.end;

      fprintf(stderr, "start loop. top = (%d, %d, %d). t = %d\n", node, beg, end, t);

      if (beg == end)
	{
	  fprintf(stderr, "base case. m[%d] := a[%d] = %d \n", node, beg, a[beg]);
	  m[node] = a[beg];
	  pop(stack, t);
	  fprintf(stderr, "pop, t = %d\n", t);
	}
      else
	{
	  left_child = 2*node + 1;
	  right_child = 2*node + 2;
	  mid = (beg + end)/2;

	  assert (right_child <= SIZE);

	  fprintf(stderr, "left_child=%d, right_child=%d, mid=%d\n", left_child, right_child, mid);
	  
	  if ((m[left_child] > 0) && (m[right_child] > 0))
	    {
	      m[node] = min(m[left_child], m[right_child]);
	      pop(stack, t);
	      fprintf(stderr, "Children not NULL, m[%d] = min(m[%d], m[%d]) = %d\n", node, left_child, right_child, m[node]);
	    }
	  else
	    {
	      if (m[left_child] == 0)
		{
		  push(stack, t, SIZE, left_child, beg, mid);
		  fprintf(stderr, "Left child is NULL, push(%d, %d, %d). t = %d\n", left_child, beg, mid, t);
		}
	      
	      if (m[right_child] == 0)
		{
		  push(stack, t, SIZE, right_child, mid+1, end);
		  fprintf(stderr, "Right child is NULL, push(%d, %d, %d). t = %d\n", right_child, mid+1, end, t);
		}
	    }
	}
    }
}




// ****************************************************************
struct FunctionCall
{
  int parent_address;
  std::size_t my_offset;
  std::size_t my_address;
  std::size_t node;
  std::size_t beg;
  std::size_t end;
};



FunctionCall&
top(FunctionCall *stack, const std::size_t t)
{
  assert (t > 0);
  return stack[t-1];
}



void
push(FunctionCall *stack, std::size_t& t, const std::size_t bound,
     int pa, std::size_t ma, std::size_t mo,
     std::size_t n, std::size_t b, std::size_t e)
{
  if (t == bound)
    {
      fprintf(stderr, "Stack overflow!\n");
      exit (1);
    }

  stack[t].parent_address = pa;
  stack[t].my_offset = mo;
  stack[t].my_address = ma;
  stack[t].node = n;
  stack[t].beg = b;
  stack[t].end = e;
  ++t;
}



void
pop(FunctionCall *stack, std::size_t& t)
{
  if (t == 0)
    {
      fprintf(stderr, "Stack underflow!\n");
      exit (1);
    }

  --t;
}



void
print(FunctionCall *stack, const std::size_t t)
{
  if (t > 0)
    {
      for (std::size_t i = t; i > 0; --i)
	{
	  fprintf(stderr, "%d %u %u %u %u %u\n", 
		  stack[i-1].parent_address, 
		  stack[i-1].my_offset, 
		  stack[i-1].my_address, 
		  stack[i-1].node, 
		  stack[i-1].beg, 
		  stack[i-1].end);
	}
    }
  fprintf(stderr, "BOTTOM\n");
}



std::size_t
query(std::size_t* m, const std::size_t SIZE, std::size_t n, std::size_t i, std::size_t j)
{
  std::size_t node;
  int parent_address;
  std::size_t my_offset;
  std::size_t my_address;
  std::size_t left_child;
  std::size_t right_child;
  std::size_t beg;
  std::size_t end;
  std::size_t mid;
  std::size_t address = 0;

  int ret[SIZE][2];
  for (std::size_t k = 0; k < SIZE; ++k)
    {
      ret[k][0] = ret[k][1] = 0;
    }

  FunctionCall stack[SIZE];
  std::size_t t = 0;

  push(stack, t, SIZE, -1, 0, 0, 0, 0, n-1);

  while (t > 0)
    {
      FunctionCall& current_range = top(stack, t);
      parent_address = current_range.parent_address;
      my_address = current_range.my_address;
      my_offset = current_range.my_offset;
      node = current_range.node;
      beg = current_range.beg;
      end = current_range.end;

      fprintf(stderr, "Looking at (%d %d %d %d %d %d)\n", parent_address, my_address, my_offset, node, beg, end);

      if ((i > end) || (j < beg))
	{
	  assert (my_address != 0);
	  assert (ret[parent_address][my_offset] == 0);
	  ret[parent_address][my_offset] = -1;
	  pop(stack, t);
	  fprintf(stderr, "Disjoint with [%d,%d]. ret[%d][%d] := -1. pop from stack\n", i, j, parent_address, my_offset);
	  continue;
	}

      if ((beg >= i) && (end <= j))
	{
	  if (parent_address == -1)
	    {
	      assert (t == 1);
	      return m[node];
	    }
	  else
	    {
	      assert (ret[parent_address][my_offset] == 0);	      
	      ret[parent_address][my_offset] = m[node];
	      pop(stack, t);
	      fprintf(stderr, "Contained in [%d,%d]. ret[%d][%d] = m[%d] = %d. pop from stack", i, j, parent_address, my_offset, node, m[node]);
	      continue;
	    }
	}

      // calling mode
      if ((ret[my_address][0] == 0) && (ret[my_address][1] == 0))
	{
	  left_child = 2*node + 1;
	  right_child = 2*node + 2;
	  mid = (beg + end)/2;

	  fprintf(stderr, "Calling mode. Pushing (%d %d %d %d %d %d)\n", my_address, address+1, 0, left_child, beg, mid);
	  push(stack, t, SIZE, my_address, ++address, 0, left_child, beg, mid);

	  fprintf(stderr, "Calling mode. Pushing (%d %d %d %d %d %d)\n", my_address, address+1, 1, right_child, mid+1, end);
	  push(stack, t, SIZE, my_address, ++address, 1, right_child, mid+1, end);

	  fprintf(stderr, "stack:\n");
	  print(stack, t);
	}
      // receiving mode
      // return the right value to the parent call
      else
	{
	  fprintf(stderr, "Receiving mode. ");
	  assert ((ret[my_address][0] != 0) && (ret[my_address][1] != 0));
	  if (ret[my_address][0] == -1)
	    {
	      fprintf(stderr, "offset[0] = -1. Return offset[1] = %d\n", ret[my_address][1]);
	      ret[parent_address][my_offset] = ret[my_address][1];
	    }
	  else if (ret[my_address][1] == -1)
	    {
	      fprintf(stderr, "offset[1] = -1. Return offset[0] = %d\n", ret[my_address][0]);
	      ret[parent_address][my_offset] = ret[my_address][0];
	    }
	  else
	    {
	      fprintf(stderr, "Return min(%d,%d) = %d\n", ret[my_address][0], ret[my_address][1], min(ret[my_address][0], ret[my_address][1]));
	      if (parent_address == -1)
		{
		  return min(ret[my_address][0], ret[my_address][1]);
		}
	      ret[parent_address][my_offset] = min(ret[my_address][0], ret[my_address][1]);
	    }
	  pop(stack, t);
	}
    }
}



int 
main(int argc, char* argv[])
{
  srand( time(NULL) );

  std::size_t n;
  std::size_t i;
  std::size_t j;

  if (argc < 4)
    {
      n = 10;
      i = (std::size_t)atoi(argv[1]);
      j = (std::size_t)atoi(argv[2]);
    }
  else
    {
      n = (std::size_t)atoi(argv[1]);
      i = (std::size_t)atoi(argv[2]);
      j = (std::size_t)atoi(argv[3]);
    }

  std::size_t a[n];
  for (std::size_t k = 0; k < n; ++k)
    {
      a[k] = rand() % 10 + 1;
      fprintf(stderr, "%d ", a[k]);
    }
  fprintf(stderr, "\n");

  //  std::size_t a[10] = {6, 8, 1, 9, 4, 6, 3, 2, 4, 7};

  // the array which contain the segment tree
  const std::size_t SIZE = 4*n;
  std::size_t m[SIZE];
  for (std::size_t k = 0; k < SIZE; ++k)
    {
      m[k] = 0;
    }

  create_segment_tree(m, a, SIZE, n);

  std::size_t val = query(m, SIZE, n, i, j);

  fprintf(stderr, "\n\nm:\n");
  for (std::size_t k = 0; k < SIZE; ++k)
    {
      fprintf(stderr, "%d ", m[k]);
    }
  fprintf(stderr, "\n\na:\n");

  for (std::size_t k = 0; k < n; ++k)
    {
      fprintf(stderr, "%d ", a[k]);
    }
  fprintf(stderr, "\n");

  fprintf(stderr, "\n\n[%d,%d]:\n",i,j);
  for (std::size_t k = i; k <= j; ++k)
    {
      fprintf(stderr, "%d ", a[k]);
    }
  fprintf(stderr, "\n");

  fprintf(stderr, "Min = %d\n", val);  
}
